#!/usr/bin/env python

import sys


class SudokuBoard:
    SIZE = 9
    BLOCKSIZE = 3
    def __init__(self):
        self.cells = {}

    def set(self, row, column, value):
        self.cells[(row, column)] = int(value)

    def getCellValue(self, i, j):
        return self.cells.get((i,j,), '.')
    
    def __repr__(self):
        result = ''
        for i in range(SudokuBoard.SIZE):
            for j in range(SudokuBoard.SIZE):
                result += str(self.getCellValue(i, j))
            result += '\n'
        return result

    def isInRow(self, rowIndex, value):
        for col in range(SudokuBoard.SIZE):
            if self.getCellValue(rowIndex, col) == value:
                return True
        return False

    def isInColumn(self, colIndex, value):
        for row in range(SudokuBoard.SIZE):
            if self.getCellValue(row, colIndex) == value:
                return True
        return False

    def isInSameBlock(self, row, col, value):
        value = int(value)
        row = SudokuBoard.BLOCKSIZE * int(row/SudokuBoard.BLOCKSIZE)
        col = SudokuBoard.BLOCKSIZE * int(col/SudokuBoard.BLOCKSIZE)

        for i in range(row, row+SudokuBoard.BLOCKSIZE):
            for j in range(col, col+SudokuBoard.BLOCKSIZE):
                if self.cells.get((i, j)) == value:
                    return True
        return False

    def isSolved(self):
        return SudokuBoard.SIZE * SudokuBoard.SIZE == len(self.cells)

    def possibleValues(self, row, col):
        if (row, col) in self.cells:
            return [self.cells[(row,col)]]
        
        results = []
        for i in range(1, SudokuBoard.SIZE+1):
            if not self.isInRow(row, i) and \
               not self.isInColumn(col, i) and \
               not self.isInSameBlock(row, col, i):
                results.append(i)
        return results

    def fillInObviousCells(self):
        for i in range(SudokuBoard.SIZE):
            for j in range(SudokuBoard.SIZE):
                possibleValues = self.possibleValues(i, j)
                if len(possibleValues) == 1:
                    self.set(i, j, possibleValues[0])
                    
                    
    def solve(self):
        prevNumFullCells = -1
        numFullCells = len(self.cells)
        while prevNumFullCells != numFullCells:
            prevNumFullCells = numFullCells
            self.fillInObviousCells()
            numFullCells = len(self.cells)


def read(source):
    inputString = ''.join(source.read().split())
    board = SudokuBoard()
    cellNumber = 0
    for char in inputString:
        if char != '.':
            board.set(cellNumber / 9, cellNumber % 9, char)
        cellNumber += 1
    return board


def main(args=None):
    if args == None:
        args = sys.argv[1:]

    print args[0]
    board = read(file(args[0]))
    print board
    board.solve()
    print board
    return 0


if __name__ == '__main__':
    sys.exit(main())

